1. Field of the Invention
The present invention relates to passing routing information among mobile intermediate network nodes, such as in a wireless mobile ad hoc network (MANET).
2. Description of the Related Art
Networks of general purpose computer systems and specialized devices connected by external communication links are well known and widely used in commerce. The networks often include one or more network devices that facilitate the passage of information between the computer systems and devices. A network node is a network device or computer or specialized device connected by the communication links. An end node is a node that is configured to originate or terminate communications over the network. An intermediate network node facilitates the passage of data between end nodes.
Communications between nodes are typically effected by exchanging discrete packets of data. Information is exchanged within data packets according to one or more of many well known, new or still developing protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other based on information sent over the communication links. Each packet typically comprises 1] header information associated with a particular protocol, and 2] payload information that follows the header information and contains information that may be processed independently of that particular protocol. In some protocols, the packet includes 3] trailer information following the payload and indicating the end of the payload information. The header includes information such as the source of the packet, its destination, the length of the payload, and other properties used by the protocol. Often, the data in the payload for the particular protocol includes a header and payload for a different protocol associated with a different layer of detail for information exchange. The protocol in the payload is said to be encapsulated in the protocol of the header for the payload.
The headers included in a packet traversing multiple heterogeneous networks, such as the Internet, typically include a physical (layer 1) header, a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The internetwork header provides information defining the source and destination address within the network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the end node assigned to the destination IP address stored in the packet's internetwork header.
Routers and switches are network devices that determine which communication link or links to employ to support the progress of data packets through the network. A network node that determines which links to employ based on information in the internetwork header (layer 3) is called a router.
Some protocols pass protocol-related information among two or more network nodes in special control packets that are communicated separately and which include a payload of information used by the protocol itself rather than a payload of data to be communicated for another application. These control packets and the processes at network nodes that utilize the control packets are said to be in another dimension, a “control plane,” distinct from the “data plane” dimension that includes the data packets with payloads for other applications at the end nodes.
A link-state protocol is an example of a routing protocol, which only exchanges control plane messages used for routing data packets sent in a different routed protocol (e.g., IP). To reduce the consumption of network resources and improve scalability, some routing protocols divide a large network up into smaller subnetworks. For example, the OSI protocol suite and the Open Shortest Path First (OSPF) routing protocol divide a network into autonomous systems and areas. An autonomous system (AS) is a portion of a network under the network administration of a single authority, such as an enterprise or Internet service provider (ISP). An AS is divided into areas. Each area is a group of contiguous subnetworks and attached end nodes specified by a network administrator, usually manually. In OSI, routers within an AS communicate with each other using an intermediate system to intermediate system (IS-IS) protocol. According to IS-IS, routing within an area (level 1 routing) uses link-state data that distinguishes each link on each router in the area. Routing between areas (level 2 routing) goes through a level 2 router that aggregates the addresses reachable through that level 2 router. By aggregating routing information for addresses reachable over many links of a level 2 router, the amount of network resources consumed to maintain link-state data and make routing decisions can be reduced and network scalability can be enhanced. The division of routers into areas is conventionally a manual process performed by human network administrators.
Mobile ad-hoc networks (MANETs) involve mobile routers that can join and depart a network or area using wireless communications links. Each router is configured with an area, called herein a configured area or a base area, when the router is configured for routing network communications. Mobile routers are given a base area that matches the bane area given to other routers expected to operate closely together because of some affinity that can be identified, such as ownership by a particular enterprise or organization. For example, all mobile routers for a municipal fire, rescue and police department are configured with the same base area.
According to existing routing protocols, a router, including a mobile router, accepts attempts by an adjacent router that belongs to the same area to form an adjacency relationship and initiate an exchange of routing information for the area. Such attempts begin, for example, in OSPF with a HELLO message that includes data that indicates the area to which the router that sends the HELLO message belongs. After an adjacency relationship is formed, all detailed routing information for the area is exchanged according to level one routing.
While suitable for manually configured and strictly managed networks, this approach suffers some deficiencies when applied in a MANET context, in which the number of adjacent mobile routers in an area is not under control of a network administrator, but instead subject to operational considerations. For example, the number of routers belonging to an area may exceed the number at which the network operates efficiently, and cause the network to devote much or most of its resources to passing routing information. With mobile routers, the amount of information that is expected to be passed during a particular time interval is greater than in wired networks in which router adjacencies are relatively stable. As routers move quickly in a MANET, adjacencies are made and broken often, thus changing network topology and causing the flooding of detailed routing information across all routers belonging to the routing area. For example, during a crisis, fire, rescue and police entities, with their mobile routers, converge on a scene of the crisis. Hundreds of adjacencies are suddenly formed, dozens of which change per second as various elements of the response move into and out of range of each other. A MANET can enter a catastrophic state in which all resources are devoted to exchanging routing information in control plane packets and few or no resources are left to handle emergency information in data plane traffic.
Based on the foregoing, there is a clear need for techniques to utilize changing links by sharing routing information with other routers that belong to the same area, which techniques do not suffer the deficiencies of prior approaches.